// 基本思想： 将整数按位数切割成不同的数字，然后按每个位数分别进行排序
// 步骤： 按照最低位优先法，或者最高位优先法，最常用的最低位优先法
// 1. 遍历数组元素，获取数组最大元素，并取得位数
// 2. 定义长度为10的桶buckets，分别代表0-9这个10个数字
// 3. 以个位元素为索引，根据数组元素个位上的值，将数组元素存入对应数字的桶中
// 4. 清空原始数组，并从桶中依次取出对应元素，重新加入到原始数组中
// 5. 之后分别以十位，百位，最大值的最高位为索引


// 时间复杂度：O((n + m) * k),n是待排序元素的个数，m为桶的数量，k是数字位数
// 空间复杂度O(n + m), m为桶的数量
// 稳定排序算法

function radixSort(arr) {
    // 1. 桶的大小为所有元素的最大位数
    let size = String(Math.max(...arr)).length

    // 从低位到高位依次遍历每一位，以各个数位值为索引，对数组进行按位排序
    for (let i = 0; i < size; i++) {
        // 使用一个长度为10的桶来存放各个位上的元素
        let buckets = new Array(10).fill(0).map(_ => [])
        // 遍历数组元素，根据元素对应位上的值，将其存入对应的桶中
        for (let j = 0; j < arr.length; j++) {
            buckets[Math.floor(arr[j] / Math.pow(10, i)) % 10].push(arr[j])            
        }
        // 清空原始数组
        arr = []
        // 从桶中依次取出对应元素，并重新加入到原始数组
        for (let j = 0; j < buckets.length; j++) {
            arr.push(...buckets[j])
        }
    }
    return arr
}

let arr = [2, 7, 26, 25, 19, 17, 1, 90, 3, 36]
console.log(radixSort(arr));